2007 · 94 citations · 23 references
ComputingComputer ScienceData StructuresDatabasesInformation RetrievalQuery ProcessingSearch SystemsSearching AlgorithmsDynamic IndexingIndexingScalable IndexingSearch OptimizationTemporal IndexingTemporal Query OptimizationTemporal Query Processing
Text search over temporally versioned document collections such as web archives has received little attention as a research problem. As a consequence, there is no scalable and principled solution to search such a collection as of a specified time. In this work, we address this shortcoming and propose an efficient solution for time-travel text search by extending the inverted file index to make it ready for temporal search. We introduce approximate temporal coalescing as a tunable method to reduce the index size without significantly affecting the quality of results. In order to further improve the performance of time-travel queries, we introduce two principled techniques to trade off index size for its performance. These techniques can be formulated as optimization problems that can be solved to near-optimality. Finally, our approach is evaluated in a comprehensive series of experiments on two large-scale real-world datasets. Results unequivocally show that our methods make it possible to build an efficient "time machine" scalable to large versioned text collections.
23
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
A Language Modeling Approach to Information Retrieval
Jay Ponte, W. Bruce Croft · ACM SIGIR Forum · 2017 · 2.5K citations · Full text
A language modeling approach to information retrieval
Jay Ponte, W. Bruce Croft · 1998 · 1.7K citations
An online algorithm for segmenting time series
Eamonn Keogh, S. Chu, David M. Hart et al. · 2002 · 1.1K citations
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · Journal of Computer and System Sciences · 2003 · 941 citations