-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathpaper.aux
92 lines (92 loc) · 6.86 KB
/
paper.aux
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
\relax
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\citation{Burks:2014}
\citation{Cormode:2005}
\citation{Matusevych:2012}
\citation{MITNews2012}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}{section.1}}
\newlabel{sec:Intro}{{1}{1}{Introduction}{section.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Problem Statement}{1}{subsection.1.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Previous Work}{1}{subsection.1.2}}
\newlabel{sec:PreviousWork}{{1.2}{1}{Previous Work}{subsection.1.2}{}}
\citation{Matusevych:2012}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Our Approaches}{2}{subsection.1.3}}
\newlabel{eq:threshold}{{1}{2}{Our Approaches}{equation.1.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Describing the History-Sensitive Algorithm and Data Structure}{2}{section.2}}
\citation{Matusevych:2012}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Data Structures}{3}{subsection.2.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.1}History Data Structure}{3}{subsubsection.2.1.1}}
\newlabel{eq:kernel}{{2}{3}{History Data Structure}{equation.2.2}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.2}Current-Window Data Structure}{3}{subsubsection.2.1.2}}
\newlabel{eq:priority}{{3}{3}{Current-Window Data Structure}{equation.2.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Algorithm Pseudocode}{3}{subsection.2.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1}Updating History Data Structure}{3}{subsubsection.2.2.1}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Update History\relax }}{4}{algorithm.1}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{alg1}{{1}{4}{Update History\relax }{algorithm.1}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2}Updating heap and hash tables}{4}{subsubsection.2.2.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.3}Finding the trending hashtags}{4}{subsubsection.2.2.3}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Analyzing the History-Sensitive Algorithm}{4}{section.3}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Variables referenced in this section\relax }}{4}{table.caption.1}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Update Current-Window\relax }}{5}{algorithm.2}}
\newlabel{alg2}{{2}{5}{Update Current-Window\relax }{algorithm.2}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {3}{\ignorespaces Top $k$ trending hashtags\relax }}{5}{algorithm.3}}
\newlabel{alg3}{{3}{5}{Top $k$ trending hashtags\relax }{algorithm.3}{}}
\citation{Matusevych:2012}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Correctness}{6}{subsection.3.1}}
\newlabel{sec:Correctness}{{3.1}{6}{Correctness}{subsection.3.1}{}}
\newlabel{eq:approxpriority}{{4}{6}{Correctness}{equation.3.4}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Runtime Analysis}{6}{subsection.3.2}}
\citation{Matusevych:2012}
\newlabel{my-label}{{\caption@xref {my-label}{ on input line 381}}{7}{Runtime Analysis}{table.caption.2}{}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Time analysis summary\relax }}{7}{table.caption.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Spatial Analysis}{7}{subsection.3.3}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Design Choices}{7}{section.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Choosing the parameters $y$ and $z$}{7}{subsection.4.1}}
\citation{Matusevych:2012}
\citation{Twitter2014}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Parameters of the History Data Structure}{8}{subsection.4.2}}
\newlabel{eq:error_control}{{5}{8}{Parameters of the History Data Structure}{equation.4.5}{}}
\newlabel{eq:certainty_control}{{6}{8}{Parameters of the History Data Structure}{equation.4.6}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Choosing the Flavor of Heap}{8}{subsection.4.3}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Testing Procedure}{8}{section.5}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Results}{8}{section.6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Runtime Measurements}{8}{subsection.6.1}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Distribution of Jaccard Similarities\relax }}{9}{figure.caption.3}}
\newlabel{fig:jaccard_sims}{{1}{9}{Distribution of Jaccard Similarities\relax }{figure.caption.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Are the Algorithm Outputs Actually Trending?}{9}{subsection.6.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.1}The Intersection Distribution}{9}{subsubsection.6.2.1}}
\newlabel{eq:jaccard}{{7}{9}{The Intersection Distribution}{equation.6.7}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.2}Checking the Algorithm-Defined Trends Against Real Life}{9}{subsubsection.6.2.2}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces News Visualization of Trending Tweets\relax }}{10}{figure.caption.4}}
\newlabel{fig:news_vis}{{2}{10}{News Visualization of Trending Tweets\relax }{figure.caption.4}{}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Discussion}{10}{section.7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.1}Comparison of Naive and History-Sensitive Algorithms}{10}{subsection.7.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2}Applicability to Real-Time Data}{11}{subsection.7.2}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Future Work}{11}{section.8}}
\newlabel{sec:Future Work}{{8}{11}{Future Work}{section.8}{}}
\@writefile{toc}{\contentsline {section}{\numberline {9}Appendix I: Code and Visualizations}{11}{section.9}}
\newlabel{sec:Appendix_code_viz}{{9}{11}{Appendix I: Code and Visualizations}{section.9}{}}
\bibcite{Burks:2014}{Burks2014}
\bibcite{Cormode:2005}{Cormode2005}
\bibcite{MITNews2012}{MITNews2012}
\bibcite{Matusevych:2012}{Matusevych2012}
\bibcite{Twitter2014}{Twitter2014}
\@writefile{toc}{\contentsline {section}{\numberline {10}Appendix II: Top-$k$ Hashtags Results}{12}{section.10}}
\newlabel{sec:Appendix_topk}{{10}{12}{Appendix II: Top-$k$ Hashtags Results}{section.10}{}}