2003 · 48 citations · 9 references
ComputingComputer ScienceData ManagementDatabasesMemoryDatabase ManagementNearest Neighbor SearchQuery ManagementQuery OptimizationQuery ProcessingRange SearchingAccessApproximate Range SearchingHigh-recall SearchQuery Performance OptimizationRange QueriesSelectivity EstimationTop-k Query OptimizationTop-k Query Processing
Top-k queries arise naturally in many database applications that require searching for records whose attribute values are close to those specified in a query. We study the problem of processing a top-k query by translating it into an approximate range query that can be efficiently processed by traditional relational DBMSs. We propose a sampling-based approach, along with various query mapping strategies, to determine a range query that yields high recall with low access cost. Our experiments on real-world datasets show that, given the same memory budgets, our sampling-based estimator outperforms a previous histogram-based method in terms of access cost, while achieving the same level of recall. Furthermore, unlike the histogram-based approach, our sampling-based query mapping scheme scales well for high dimensional data and is easy to implement with low maintenance cost.
9
Indexing by latent semantic analysis
Scott Deerwester, Susan Dumais, George W. Furnas et al. · Journal of the American Society for Information Science · 1990 · 12.8K citations
Similarity Search in High Dimensions via Hashing
Aristides Gionis, Piotr Indyk, Rajeev Motwani · 1999 · 3.1K citations
Norio Katayama, Shin’ichi Satoh · 1997 · 820 citations
Similarity indexing with the SS-tree
David A. White, Ramesh Jain · 2002 · 639 citations
Fuzzy queries in multimedia database systems
Ronald Fagin · 1998 · 299 citations · Full text