mirror of
https://github.com/hanzoai/papers.git
synced 2026-10-22 17:20:17 +00:00
zeekayandHanzo Dev
03c6289dfc
Design, prior art and a measurement protocol for a weighted inverted index over a mixed sparse basis and part-level routing before per-part HNSW in a ClickHouse-derived store. Each component is marked prior art or proposed. The protocol fits C(N) = aN^alpha to parts, granules and bytes touched per correct answer at a held recall. No numbers: every results cell is a placeholder read from results-data.tex until the baseline lane writes it. Co-authored-by: Hanzo Dev <[email protected]>
763 lines
27 KiB
BibTeX
763 lines
27 KiB
BibTeX
% References for hanzo-sparse-basis-routing.
|
|
%
|
|
% A line beginning "% TODO" marks an entry whose details we did not verify
|
|
% against the publisher's record. Everything not so marked is cited from fields we are
|
|
% confident of; page ranges we were unsure of are omitted rather than guessed.
|
|
|
|
@article{zobel2006inverted,
|
|
author = {Justin Zobel and Alistair Moffat},
|
|
title = {Inverted Files for Text Search Engines},
|
|
journal = {ACM Computing Surveys},
|
|
volume = {38},
|
|
number = {2},
|
|
year = {2006}
|
|
}
|
|
|
|
@article{robertson2009bm25,
|
|
author = {Stephen Robertson and Hugo Zaragoza},
|
|
title = {The Probabilistic Relevance Framework: {BM25} and Beyond},
|
|
journal = {Foundations and Trends in Information Retrieval},
|
|
volume = {3},
|
|
number = {4},
|
|
pages = {333--389},
|
|
year = {2009}
|
|
}
|
|
|
|
@inproceedings{broder2003wand,
|
|
author = {Andrei Z. Broder and David Carmel and Michael Herscovici and
|
|
Aya Soffer and Jason Zien},
|
|
title = {Efficient Query Evaluation using a Two-Level Retrieval Process},
|
|
booktitle = {Proceedings of the 12th ACM Conference on Information and
|
|
Knowledge Management (CIKM)},
|
|
pages = {426--434},
|
|
year = {2003}
|
|
}
|
|
|
|
@inproceedings{ding2011bmw,
|
|
author = {Shuai Ding and Torsten Suel},
|
|
title = {Faster Top-k Document Retrieval Using Block-Max Indexes},
|
|
booktitle = {Proceedings of the 34th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
pages = {993--1002},
|
|
year = {2011}
|
|
}
|
|
|
|
@article{turtle1995maxscore,
|
|
author = {Howard Turtle and James Flood},
|
|
title = {Query Evaluation: Strategies and Optimizations},
|
|
journal = {Information Processing and Management},
|
|
volume = {31},
|
|
number = {6},
|
|
pages = {831--850},
|
|
year = {1995}
|
|
}
|
|
|
|
@inproceedings{mallia2017vbmw,
|
|
author = {Antonio Mallia and Giuseppe Ottaviano and Elia Porciani and
|
|
Nicola Tonellotto and Rossano Venturini},
|
|
title = {Faster {BlockMax} {WAND} with Variable-sized Blocks},
|
|
booktitle = {Proceedings of the 40th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2017}
|
|
}
|
|
|
|
@article{fagin2003ta,
|
|
author = {Ronald Fagin and Amnon Lotem and Moni Naor},
|
|
title = {Optimal Aggregation Algorithms for Middleware},
|
|
journal = {Journal of Computer and System Sciences},
|
|
volume = {66},
|
|
number = {4},
|
|
pages = {614--656},
|
|
year = {2003}
|
|
}
|
|
|
|
% TODO: verify the page range of Anh and Moffat, SIGIR 2002.
|
|
@inproceedings{anh2002impact,
|
|
author = {Vo Ngoc Anh and Alistair Moffat},
|
|
title = {Impact Transformation: Effective and Efficient Web Retrieval},
|
|
booktitle = {Proceedings of the 25th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2002}
|
|
}
|
|
|
|
@inproceedings{lin2015anytime,
|
|
author = {Jimmy Lin and Andrew Trotman},
|
|
title = {Anytime Ranking for Impact-Ordered Indexes},
|
|
booktitle = {Proceedings of the 2015 International Conference on the Theory
|
|
of Information Retrieval (ICTIR)},
|
|
year = {2015}
|
|
}
|
|
|
|
% TODO: verify the venue details of PISA (OSIRRC 2019 workshop proceedings,
|
|
% CEUR-WS volume and pages).
|
|
@inproceedings{mallia2019pisa,
|
|
author = {Antonio Mallia and Micha{\l} Siedlaczek and Joel Mackenzie and
|
|
Torsten Suel},
|
|
title = {{PISA}: Performant Indexes and Search for Academia},
|
|
booktitle = {Proceedings of the Open-Source IR Replicability Challenge
|
|
(OSIRRC) at SIGIR},
|
|
year = {2019}
|
|
}
|
|
|
|
@inproceedings{formal2021splade,
|
|
author = {Thibault Formal and Benjamin Piwowarski and
|
|
St{\'e}phane Clinchant},
|
|
title = {{SPLADE}: Sparse Lexical and Expansion Model for First Stage
|
|
Ranking},
|
|
booktitle = {Proceedings of the 44th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
pages = {2288--2292},
|
|
year = {2021}
|
|
}
|
|
|
|
@misc{formal2021spladev2,
|
|
author = {Thibault Formal and Carlos Lassance and
|
|
Benjamin Piwowarski and St{\'e}phane Clinchant},
|
|
title = {{SPLADE} v2: Sparse Lexical and Expansion Model for
|
|
Information Retrieval},
|
|
howpublished = {arXiv:2109.10086},
|
|
year = {2021}
|
|
}
|
|
|
|
@inproceedings{formal2022spladepp,
|
|
author = {Thibault Formal and Carlos Lassance and Benjamin Piwowarski and
|
|
St{\'e}phane Clinchant},
|
|
title = {From Distillation to Hard Negative Sampling: Making Sparse
|
|
Neural {IR} Models More Effective},
|
|
booktitle = {Proceedings of the 45th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2022}
|
|
}
|
|
|
|
@inproceedings{gao2021coil,
|
|
author = {Luyu Gao and Zhuyun Dai and Jamie Callan},
|
|
title = {{COIL}: Revisit Exact Lexical Match in Information Retrieval
|
|
with Contextualized Inverted List},
|
|
booktitle = {Proceedings of the 2021 Conference of the North American
|
|
Chapter of the Association for Computational Linguistics
|
|
(NAACL)},
|
|
pages = {3030--3042},
|
|
year = {2021}
|
|
}
|
|
|
|
@misc{lin2021unicoil,
|
|
author = {Jimmy Lin and Xueguang Ma},
|
|
title = {A Few Brief Notes on {DeepImpact}, {COIL}, and a Conceptual
|
|
Framework for Information Retrieval Techniques},
|
|
howpublished = {arXiv:2106.14807},
|
|
year = {2021}
|
|
}
|
|
|
|
@inproceedings{mallia2021deepimpact,
|
|
author = {Antonio Mallia and Omar Khattab and Torsten Suel and
|
|
Nicola Tonellotto},
|
|
title = {Learning Passage Impacts for Inverted Indexes},
|
|
booktitle = {Proceedings of the 44th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
pages = {1723--1727},
|
|
year = {2021}
|
|
}
|
|
|
|
@inproceedings{dai2020deepct,
|
|
author = {Zhuyun Dai and Jamie Callan},
|
|
title = {Context-Aware Term Weighting For First Stage Passage Retrieval},
|
|
booktitle = {Proceedings of the 43rd International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
pages = {1533--1536},
|
|
year = {2020}
|
|
}
|
|
|
|
% TODO: verify the arXiv identifier 2110.11540 for the Mackenzie, Trotman and
|
|
% Lin note on learned sparse weights.
|
|
@misc{mackenzie2021wacky,
|
|
author = {Joel Mackenzie and Andrew Trotman and Jimmy Lin},
|
|
title = {Wacky Weights in Learned Sparse Representations and the
|
|
Revenge of Score-at-a-Time Query Evaluation},
|
|
howpublished = {arXiv:2110.11540},
|
|
year = {2021}
|
|
}
|
|
|
|
@inproceedings{lassance2022efficiency,
|
|
author = {Carlos Lassance and St{\'e}phane Clinchant},
|
|
title = {An Efficiency Study for {SPLADE} Models},
|
|
booktitle = {Proceedings of the 45th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2022}
|
|
}
|
|
|
|
% TODO: verify authors, pages and venue of the guided-traversal paper
|
|
% (SIGIR 2022).
|
|
@inproceedings{mallia2022guided,
|
|
author = {Antonio Mallia and Joel Mackenzie and Torsten Suel and
|
|
Nicola Tonellotto},
|
|
title = {Faster Learned Sparse Retrieval with Guided Traversal},
|
|
booktitle = {Proceedings of the 45th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2022}
|
|
}
|
|
|
|
% TODO: verify authors and venue of the block-max pruning paper (SIGIR 2024).
|
|
@inproceedings{mallia2024bmp,
|
|
author = {Antonio Mallia and Torsten Suel and Nicola Tonellotto},
|
|
title = {Faster Learned Sparse Retrieval with Block-Max Pruning},
|
|
booktitle = {Proceedings of the 47th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2024}
|
|
}
|
|
|
|
% TODO: verify the page range and exact title of the Seismic paper (SIGIR 2024).
|
|
@inproceedings{bruch2024seismic,
|
|
author = {Sebastian Bruch and Franco Maria Nardini and Cosimo Rulli and
|
|
Rossano Venturini},
|
|
title = {Efficient Inverted Indexes for Approximate Retrieval over
|
|
Learned Sparse Representations},
|
|
booktitle = {Proceedings of the 47th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2024}
|
|
}
|
|
|
|
@article{salton1975vsm,
|
|
author = {Gerard Salton and Anita Wong and Chung-Shu Yang},
|
|
title = {A Vector Space Model for Automatic Indexing},
|
|
journal = {Communications of the ACM},
|
|
volume = {18},
|
|
number = {11},
|
|
pages = {613--620},
|
|
year = {1975}
|
|
}
|
|
|
|
@inproceedings{gabrilovich2007esa,
|
|
author = {Evgeniy Gabrilovich and Shaul Markovitch},
|
|
title = {Computing Semantic Relatedness using {Wikipedia}-based Explicit
|
|
Semantic Analysis},
|
|
booktitle = {Proceedings of the 20th International Joint Conference on
|
|
Artificial Intelligence (IJCAI)},
|
|
pages = {1606--1611},
|
|
year = {2007}
|
|
}
|
|
|
|
@inproceedings{xiong2017duet,
|
|
author = {Chenyan Xiong and Jamie Callan and Tie-Yan Liu},
|
|
title = {Word-Entity Duet Representations for Document Ranking},
|
|
booktitle = {Proceedings of the 40th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2017}
|
|
}
|
|
|
|
@inproceedings{dalton2014entity,
|
|
author = {Jeffrey Dalton and Laura Dietz and James Allan},
|
|
title = {Entity Query Feature Expansion using Knowledge Base Links},
|
|
booktitle = {Proceedings of the 37th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
pages = {365--374},
|
|
year = {2014}
|
|
}
|
|
|
|
@misc{cox2012trigram,
|
|
author = {Russ Cox},
|
|
title = {Regular Expression Matching with a Trigram Index, or How
|
|
{Google} Code Search Worked},
|
|
howpublished = {\url{https://swtch.com/~rsc/regexp/regexp4.html}},
|
|
year = {2012}
|
|
}
|
|
|
|
@article{milo2002motifs,
|
|
author = {Ron Milo and Shai Shen-Orr and Shalev Itzkovitz and
|
|
Nadav Kashtan and Dmitri Chklovskii and Uri Alon},
|
|
title = {Network Motifs: Simple Building Blocks of Complex Networks},
|
|
journal = {Science},
|
|
volume = {298},
|
|
number = {5594},
|
|
pages = {824--827},
|
|
year = {2002}
|
|
}
|
|
|
|
@article{olshausen1996sparse,
|
|
author = {Bruno A. Olshausen and David J. Field},
|
|
title = {Emergence of Simple-Cell Receptive Field Properties by Learning a
|
|
Sparse Code for Natural Images},
|
|
journal = {Nature},
|
|
volume = {381},
|
|
number = {6583},
|
|
pages = {607--609},
|
|
year = {1996}
|
|
}
|
|
|
|
@misc{cunningham2023sae,
|
|
author = {Hoagy Cunningham and Aidan Ewart and Logan Riggs and
|
|
Robert Huben and Lee Sharkey},
|
|
title = {Sparse Autoencoders Find Highly Interpretable Features in
|
|
Language Models},
|
|
howpublished = {arXiv:2309.08600},
|
|
year = {2023}
|
|
}
|
|
|
|
@article{jegou2011pq,
|
|
author = {Herv{\'e} J{\'e}gou and Matthijs Douze and Cordelia Schmid},
|
|
title = {Product Quantization for Nearest Neighbor Search},
|
|
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
|
|
volume = {33},
|
|
number = {1},
|
|
pages = {117--128},
|
|
year = {2011}
|
|
}
|
|
|
|
@inproceedings{sivic2003videogoogle,
|
|
author = {Josef Sivic and Andrew Zisserman},
|
|
title = {Video {Google}: A Text Retrieval Approach to Object Matching in
|
|
Videos},
|
|
booktitle = {Proceedings of the 9th IEEE International Conference on
|
|
Computer Vision (ICCV)},
|
|
pages = {1470--1477},
|
|
year = {2003}
|
|
}
|
|
|
|
@inproceedings{babenko2012imi,
|
|
author = {Artem Babenko and Victor Lempitsky},
|
|
title = {The Inverted Multi-Index},
|
|
booktitle = {Proceedings of the IEEE Conference on Computer Vision and
|
|
Pattern Recognition (CVPR)},
|
|
pages = {3069--3076},
|
|
year = {2012}
|
|
}
|
|
|
|
@article{johnson2021faiss,
|
|
author = {Jeff Johnson and Matthijs Douze and Herv{\'e} J{\'e}gou},
|
|
title = {Billion-Scale Similarity Search with {GPUs}},
|
|
journal = {IEEE Transactions on Big Data},
|
|
volume = {7},
|
|
number = {3},
|
|
pages = {535--547},
|
|
year = {2021}
|
|
}
|
|
|
|
@article{malkov2020hnsw,
|
|
author = {Yury A. Malkov and Dmitry A. Yashunin},
|
|
title = {Efficient and Robust Approximate Nearest Neighbor Search Using
|
|
Hierarchical Navigable Small World Graphs},
|
|
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
|
|
volume = {42},
|
|
number = {4},
|
|
pages = {824--836},
|
|
year = {2020}
|
|
}
|
|
|
|
@inproceedings{subramanya2019diskann,
|
|
author = {Suhas Jayaram Subramanya and Fnu Devvrit and Rohan Kadekodi and
|
|
Ravishankar Krishnaswamy and Harsha Vardhan Simhadri},
|
|
title = {{DiskANN}: Fast Accurate Billion-point Nearest Neighbor Search
|
|
on a Single Node},
|
|
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
|
|
year = {2019}
|
|
}
|
|
|
|
@misc{singh2021freshdiskann,
|
|
author = {Aditi Singh and Suhas Jayaram Subramanya and
|
|
Ravishankar Krishnaswamy and Harsha Vardhan Simhadri},
|
|
title = {{FreshDiskANN}: A Fast and Accurate Graph-Based {ANN} Index
|
|
for Streaming Similarity Search},
|
|
howpublished = {arXiv:2105.09613},
|
|
year = {2021}
|
|
}
|
|
|
|
% TODO: verify the author list of the SPANN paper (NeurIPS 2021).
|
|
@inproceedings{chen2021spann,
|
|
author = {Qi Chen and Bing Zhao and Haidong Wang and Mingqin Li and
|
|
Chuanjie Liu and Zengzhong Li and Mao Yang and Jingdong Wang},
|
|
title = {{SPANN}: Highly-efficient Billion-scale Approximate Nearest
|
|
Neighbor Search},
|
|
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
|
|
year = {2021}
|
|
}
|
|
|
|
@inproceedings{guo2020scann,
|
|
author = {Ruiqi Guo and Philip Sun and Erik Lindgren and Quan Geng and
|
|
David Simcha and Felix Chern and Sanjiv Kumar},
|
|
title = {Accelerating Large-Scale Inference with Anisotropic Vector
|
|
Quantization},
|
|
booktitle = {Proceedings of the 37th International Conference on Machine
|
|
Learning (ICML)},
|
|
year = {2020}
|
|
}
|
|
|
|
% TODO: verify the author list of the SOAR paper (NeurIPS 2023).
|
|
@inproceedings{sun2023soar,
|
|
author = {Philip Sun and David Simcha and Dave Dopson and Ruiqi Guo and
|
|
Sanjiv Kumar},
|
|
title = {{SOAR}: Improved Indexing for Approximate Nearest Neighbor
|
|
Search},
|
|
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
|
|
year = {2023}
|
|
}
|
|
|
|
@article{fukunaga1975branch,
|
|
author = {Keinosuke Fukunaga and Patrenahalli M. Narendra},
|
|
title = {A Branch and Bound Algorithm for Computing k-Nearest Neighbors},
|
|
journal = {IEEE Transactions on Computers},
|
|
volume = {C-24},
|
|
number = {7},
|
|
pages = {750--753},
|
|
year = {1975}
|
|
}
|
|
|
|
@inproceedings{nister2006vocabtree,
|
|
author = {David Nist{\'e}r and Henrik Stew{\'e}nius},
|
|
title = {Scalable Recognition with a Vocabulary Tree},
|
|
booktitle = {Proceedings of the IEEE Conference on Computer Vision and
|
|
Pattern Recognition (CVPR)},
|
|
pages = {2161--2168},
|
|
year = {2006}
|
|
}
|
|
|
|
@article{muja2014flann,
|
|
author = {Marius Muja and David G. Lowe},
|
|
title = {Scalable Nearest Neighbor Algorithms for High Dimensional Data},
|
|
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
|
|
volume = {36},
|
|
number = {11},
|
|
pages = {2227--2240},
|
|
year = {2014}
|
|
}
|
|
|
|
@inproceedings{ciaccia1997mtree,
|
|
author = {Paolo Ciaccia and Marco Patella and Pavel Zezula},
|
|
title = {{M-tree}: An Efficient Access Method for Similarity Search in
|
|
Metric Spaces},
|
|
booktitle = {Proceedings of the 23rd International Conference on Very Large
|
|
Data Bases (VLDB)},
|
|
pages = {426--435},
|
|
year = {1997}
|
|
}
|
|
|
|
@article{uhlmann1991metric,
|
|
author = {Jeffrey K. Uhlmann},
|
|
title = {Satisfying General Proximity/Similarity Queries with Metric Trees},
|
|
journal = {Information Processing Letters},
|
|
volume = {40},
|
|
number = {4},
|
|
pages = {175--179},
|
|
year = {1991}
|
|
}
|
|
|
|
@inproceedings{guttman1984rtree,
|
|
author = {Antonin Guttman},
|
|
title = {{R-Trees}: A Dynamic Index Structure for Spatial Searching},
|
|
booktitle = {Proceedings of the 1984 ACM SIGMOD International Conference on
|
|
Management of Data},
|
|
pages = {47--57},
|
|
year = {1984}
|
|
}
|
|
|
|
@inproceedings{weber1998quantitative,
|
|
author = {Roger Weber and Hans-J{\"o}rg Schek and Stephen Blott},
|
|
title = {A Quantitative Analysis and Performance Study for
|
|
Similarity-Search Methods in High-Dimensional Spaces},
|
|
booktitle = {Proceedings of the 24th International Conference on Very Large
|
|
Data Bases (VLDB)},
|
|
pages = {194--205},
|
|
year = {1998}
|
|
}
|
|
|
|
@inproceedings{beyer1999nn,
|
|
author = {Kevin Beyer and Jonathan Goldstein and Raghu Ramakrishnan and
|
|
Uri Shaft},
|
|
title = {When Is ``Nearest Neighbor'' Meaningful?},
|
|
booktitle = {Proceedings of the 7th International Conference on Database
|
|
Theory (ICDT)},
|
|
pages = {217--235},
|
|
year = {1999}
|
|
}
|
|
|
|
@inproceedings{indyk1998lsh,
|
|
author = {Piotr Indyk and Rajeev Motwani},
|
|
title = {Approximate Nearest Neighbors: Towards Removing the Curse of
|
|
Dimensionality},
|
|
booktitle = {Proceedings of the 30th Annual ACM Symposium on Theory of
|
|
Computing (STOC)},
|
|
pages = {604--613},
|
|
year = {1998}
|
|
}
|
|
|
|
% TODO: verify the exact title of the Indyk and Xu paper (NeurIPS 2023).
|
|
@inproceedings{indyk2023worst,
|
|
author = {Piotr Indyk and Haike Xu},
|
|
title = {Worst-case Performance of Popular Approximate Nearest Neighbor
|
|
Search Implementations: Guarantees and Limitations},
|
|
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
|
|
year = {2023}
|
|
}
|
|
|
|
@inproceedings{prokhorenkova2020graph,
|
|
author = {Liudmila Prokhorenkova and Aleksandr Shekhovtsov},
|
|
title = {Graph-based Nearest Neighbor Search: From Practice to Theory},
|
|
booktitle = {Proceedings of the 37th International Conference on Machine
|
|
Learning (ICML)},
|
|
year = {2020}
|
|
}
|
|
|
|
@article{aumuller2020annb,
|
|
author = {Martin Aum{\"u}ller and Erik Bernhardsson and
|
|
Alexander Faithfull},
|
|
title = {{ANN-Benchmarks}: A Benchmarking Tool for Approximate Nearest
|
|
Neighbor Algorithms},
|
|
journal = {Information Systems},
|
|
volume = {87},
|
|
year = {2020}
|
|
}
|
|
|
|
% TODO: complete the author list of the billion-scale challenge report; it is
|
|
% cited here with the first author only.
|
|
@inproceedings{simhadri2022bigann,
|
|
author = {Harsha Vardhan Simhadri and others},
|
|
title = {Results of the {NeurIPS'21} Challenge on Billion-Scale
|
|
Approximate Nearest Neighbor Search},
|
|
booktitle = {Proceedings of the NeurIPS 2021 Competitions and Demonstrations
|
|
Track, PMLR 176},
|
|
year = {2022}
|
|
}
|
|
|
|
% TODO: complete the author list of the Milvus paper; it is cited here with the
|
|
% first author only.
|
|
@inproceedings{wang2021milvus,
|
|
author = {Jianguo Wang and others},
|
|
title = {{Milvus}: A Purpose-Built Vector Data Management System},
|
|
booktitle = {Proceedings of the 2021 ACM SIGMOD International Conference on
|
|
Management of Data},
|
|
year = {2021}
|
|
}
|
|
|
|
% TODO: verify the venue and volume of the ACORN paper (SIGMOD 2024 /
|
|
% Proceedings of the ACM on Management of Data).
|
|
@inproceedings{patel2024acorn,
|
|
author = {Liana Patel and Peter Kraft and Carlos Guestrin and
|
|
Matei Zaharia},
|
|
title = {{ACORN}: Performant and Predicate-Agnostic Search Over Vector
|
|
Embeddings and Structured Data},
|
|
booktitle = {Proceedings of the 2024 ACM SIGMOD International Conference on
|
|
Management of Data},
|
|
year = {2024}
|
|
}
|
|
|
|
% TODO: complete the author list of Filtered-DiskANN; it is cited here with the
|
|
% first author only.
|
|
@inproceedings{gollapudi2023filtered,
|
|
author = {Siddharth Gollapudi and others},
|
|
title = {{Filtered-DiskANN}: Graph Algorithms for Approximate Nearest
|
|
Neighbor Search with Filters},
|
|
booktitle = {Proceedings of the ACM Web Conference (WWW)},
|
|
year = {2023}
|
|
}
|
|
|
|
% TODO: verify the page range of the ClickHouse VLDB paper.
|
|
@article{schulze2024clickhouse,
|
|
author = {Robert Schulze and Tom Schreiber and Ilya Yatsishin and
|
|
Ryadh Dahimene and Alexey Milovidov},
|
|
title = {{ClickHouse} --- Lightning Fast Analytics for Everyone},
|
|
journal = {Proceedings of the VLDB Endowment},
|
|
volume = {17},
|
|
number = {12},
|
|
year = {2024}
|
|
}
|
|
|
|
@misc{clickhousedocs,
|
|
author = {{ClickHouse, Inc.}},
|
|
title = {{ClickHouse} documentation and source, version 26.4:
|
|
{MergeTree} parts and granules, data skipping indexes, text
|
|
index, vector similarity index},
|
|
howpublished = {\url{https://clickhouse.com/docs}},
|
|
year = {2026},
|
|
note = {Source read at version 26.4.2.1}
|
|
}
|
|
|
|
@misc{usearch,
|
|
author = {Ash Vardanian},
|
|
title = {{USearch}: Smaller and Faster Single-File Vector Search
|
|
Engine},
|
|
howpublished = {\url{https://github.com/unum-cloud/usearch}},
|
|
year = {2023}
|
|
}
|
|
|
|
@misc{lucene,
|
|
author = {{The Apache Software Foundation}},
|
|
title = {Apache {Lucene}},
|
|
howpublished = {\url{https://lucene.apache.org}},
|
|
year = {2026}
|
|
}
|
|
|
|
@inproceedings{moerkotte1998sma,
|
|
author = {Guido Moerkotte},
|
|
title = {Small Materialized Aggregates: A Light Weight Index Structure
|
|
for Data Warehousing},
|
|
booktitle = {Proceedings of the 24th International Conference on Very Large
|
|
Data Bases (VLDB)},
|
|
pages = {476--487},
|
|
year = {1998}
|
|
}
|
|
|
|
@inproceedings{sun2014skipping,
|
|
author = {Liwen Sun and Michael J. Franklin and Sanjay Krishnan and
|
|
Reynold S. Xin},
|
|
title = {Fine-grained Partitioning for Aggressive Data Skipping},
|
|
booktitle = {Proceedings of the 2014 ACM SIGMOD International Conference on
|
|
Management of Data},
|
|
pages = {1115--1126},
|
|
year = {2014}
|
|
}
|
|
|
|
@article{oneil1996lsm,
|
|
author = {Patrick O'Neil and Edward Cheng and Dieter Gawlick and
|
|
Elizabeth O'Neil},
|
|
title = {The Log-Structured Merge-Tree ({LSM-Tree})},
|
|
journal = {Acta Informatica},
|
|
volume = {33},
|
|
number = {4},
|
|
pages = {351--385},
|
|
year = {1996}
|
|
}
|
|
|
|
@article{abadi2013columnstores,
|
|
author = {Daniel Abadi and Peter Boncz and Stavros Harizopoulos and
|
|
Stratos Idreos and Samuel Madden},
|
|
title = {The Design and Implementation of Modern Column-Oriented Database
|
|
Systems},
|
|
journal = {Foundations and Trends in Databases},
|
|
volume = {5},
|
|
number = {3},
|
|
pages = {197--280},
|
|
year = {2013}
|
|
}
|
|
|
|
@book{vanrijsbergen1979ir,
|
|
author = {C. J. van Rijsbergen},
|
|
title = {Information Retrieval},
|
|
edition = {2nd},
|
|
publisher = {Butterworths},
|
|
address = {London},
|
|
year = {1979}
|
|
}
|
|
|
|
@inproceedings{callan1995cori,
|
|
author = {James P. Callan and Zhihong Lu and W. Bruce Croft},
|
|
title = {Searching Distributed Collections with Inference Networks},
|
|
booktitle = {Proceedings of the 18th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
pages = {21--28},
|
|
year = {1995}
|
|
}
|
|
|
|
@inproceedings{si2003redde,
|
|
author = {Luo Si and Jamie Callan},
|
|
title = {Relevant Document Distribution Estimation Method for Resource
|
|
Selection},
|
|
booktitle = {Proceedings of the 26th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2003}
|
|
}
|
|
|
|
@inproceedings{aly2013taily,
|
|
author = {Robin Aly and Djoerd Hiemstra and Thomas Demeester},
|
|
title = {{Taily}: Shard Selection Using the Tail of Score Distributions},
|
|
booktitle = {Proceedings of the 36th International ACM SIGIR Conference on
|
|
Research and Development in Information Retrieval},
|
|
year = {2013}
|
|
}
|
|
|
|
@article{kulkarni2015selective,
|
|
author = {Anagha Kulkarni and Jamie Callan},
|
|
title = {Selective Search: Efficient and Effective Search of Large Textual
|
|
Collections},
|
|
journal = {ACM Transactions on Information Systems},
|
|
volume = {33},
|
|
number = {4},
|
|
year = {2015}
|
|
}
|
|
|
|
@misc{edge2024graphrag,
|
|
author = {Darren Edge and Ha Trinh and Newman Cheng and
|
|
Joshua Bradley and Alex Chao and Apurva Mody and
|
|
Steven Truitt and Jonathan Larson},
|
|
title = {From Local to Global: A Graph {RAG} Approach to
|
|
Query-Focused Summarization},
|
|
howpublished = {arXiv:2404.16130},
|
|
year = {2024}
|
|
}
|
|
|
|
@inproceedings{sarthi2024raptor,
|
|
author = {Parth Sarthi and Salman Abdullah and Aditi Tuli and
|
|
Shubh Khanna and Anna Goldie and Christopher D. Manning},
|
|
title = {{RAPTOR}: Recursive Abstractive Processing for Tree-Organized
|
|
Retrieval},
|
|
booktitle = {International Conference on Learning Representations (ICLR)},
|
|
year = {2024}
|
|
}
|
|
|
|
@article{dean2013tail,
|
|
author = {Jeffrey Dean and Luiz Andr{\'e} Barroso},
|
|
title = {The Tail at Scale},
|
|
journal = {Communications of the ACM},
|
|
volume = {56},
|
|
number = {2},
|
|
pages = {74--80},
|
|
year = {2013}
|
|
}
|
|
|
|
@book{efron1993bootstrap,
|
|
author = {Bradley Efron and Robert J. Tibshirani},
|
|
title = {An Introduction to the Bootstrap},
|
|
publisher = {Chapman and Hall},
|
|
year = {1993}
|
|
}
|
|
|
|
@article{clauset2009powerlaw,
|
|
author = {Aaron Clauset and Cosma Rohilla Shalizi and M. E. J. Newman},
|
|
title = {Power-Law Distributions in Empirical Data},
|
|
journal = {SIAM Review},
|
|
volume = {51},
|
|
number = {4},
|
|
pages = {661--703},
|
|
year = {2009}
|
|
}
|
|
|
|
@inproceedings{reimers2019sbert,
|
|
author = {Nils Reimers and Iryna Gurevych},
|
|
title = {{Sentence-BERT}: Sentence Embeddings using {Siamese}
|
|
{BERT}-Networks},
|
|
booktitle = {Proceedings of the 2019 Conference on Empirical Methods in
|
|
Natural Language Processing and the 9th International Joint
|
|
Conference on Natural Language Processing (EMNLP-IJCNLP)},
|
|
pages = {3982--3992},
|
|
year = {2019}
|
|
}
|
|
|
|
@article{kwiatkowski2019nq,
|
|
author = {Tom Kwiatkowski and Jennimaria Palomaki and Olivia Redfield and
|
|
Michael Collins and Ankur Parikh and Chris Alberti and
|
|
Danielle Epstein and Illia Polosukhin and Jacob Devlin and
|
|
Kenton Lee and Kristina Toutanova and Llion Jones and
|
|
Matthew Kelcey and Ming-Wei Chang and Andrew M. Dai and
|
|
Jakob Uszkoreit and Quoc Le and Slav Petrov},
|
|
title = {Natural Questions: A Benchmark for Question Answering Research},
|
|
journal = {Transactions of the Association for Computational Linguistics},
|
|
volume = {7},
|
|
pages = {452--466},
|
|
year = {2019}
|
|
}
|
|
|
|
@inproceedings{lee2019orqa,
|
|
author = {Kenton Lee and Ming-Wei Chang and Kristina Toutanova},
|
|
title = {Latent Retrieval for Weakly Supervised Open Domain Question
|
|
Answering},
|
|
booktitle = {Proceedings of the 57th Annual Meeting of the Association for
|
|
Computational Linguistics (ACL)},
|
|
pages = {6086--6096},
|
|
year = {2019}
|
|
}
|
|
|
|
@misc{hanzodatastore,
|
|
author = {{Hanzo Industries}},
|
|
title = {Hanzo Datastore: a fork of {ClickHouse}},
|
|
howpublished = {\url{https://github.com/hanzoai/datastore}},
|
|
year = {2026},
|
|
note = {Forked from {ClickHouse} 26.4}
|
|
}
|