Fetching the paper…
Reading the bibliography…
Given a database of bit strings $A_1,\ldots,A_m\in \{0,1\}^n$, a fundamental data structure task is to estimate the distances between a given query $B\in \{0,1\}^n$ with all the strings in the database.
Error detecting and error correcting codes
Richard W Hamming · 1950
Earlier work this paper cites.
Binary codes capable of correcting deletions, insertions and reversals
Vladimir I Levenshtein · 1966
Earlier work this paper cites.
Finding approximate patterns in strings
Esko Ukkonen · 1985
Earlier work this paper cites.
An O ( N D ) {O}({ND}) difference algorithm and its variations
Eugene W. Myers · 1986
Earlier work this paper cites.
Fast string matching with k differences
Gad M. Landau and Uzi Vishkin · 1988
Earlier work this paper cites.
Extensions to the k-means algorithm for clustering large data sets with categorical values
Zhexue Huang · 1997
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Incremental string comparison
Gad M. Landau, Eugene Wimberly Myers, and Jeanette P. Schmidt · 1998
Earlier work this paper cites.
A fuzzy k-modes algorithm for clustering categorical data
Zhexue Huang and Mingkui Ng · 1999
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Which problems have strongly exponential complexity?
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 2001
Earlier work this paper cites.
A guided tour to approximate string matching
Gonzalo Navarro · 2001
Earlier work this paper cites.
Similarity estimation techniques from rounding algorithms
Moses Charikar · 2002
Earlier work this paper cites.
Our data, ourselves: Privacy via distributed noise generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
Earlier work this paper cites.
Differential privacy
Cynthia Dwork · 2006
Earlier work this paper cites.
Multiple dimension Levenshtein edit distance calculations for evaluating automatic speech recognition systems during simultaneous speech
Jonathan G. Fiscus, Jerome Ajot, Nicolas Radde, and Christophe Laprun · 2006
Earlier work this paper cites.
Improved sketching of hamming distance with error correcting
Ely Porat and Ohad Lipsky · 2007
Earlier work this paper cites.
Privacy-preserving logistic regression
Kamalika Chaudhuri and Claire Monteleoni · 2008
Earlier work this paper cites.
Time warp edit distance with stiffness adjustment for time series matching
Pierre-François Marteau · 2009
Earlier work this paper cites.
Context dependent phonetic string edit distance for automatic speech recognition
Jasha Droppo and Alex Acero · 2010
Earlier work this paper cites.
Probabilistic inference and differential privacy
Oliver Williams and Frank McSherry · 2010
Earlier work this paper cites.
Fast search in hamming space with multi-index hashing
Mohammad Norouzi, Ali Punjani, and David J Fleet · 2012
Earlier work this paper cites.
Differential privacy for functions and functional data
Rob Hall, Alessandro Rinaldo, and Larry Wasserman · 2013
Earlier work this paper cites.
Exploiting metric structure for efficient private query release
Zhiyi Huang and Aaron Roth · 2014
Earlier work this paper cites.
Computing text similarity using tree edit distance
Grigori Sidorov, Helena Gómez-Adorno, Ilia Markov, David Pinto, and Nahun Loya · 2015
Cited alongside, same era.
Efficient genome-wide, privacy-preserving similar patient query based on private edit distance
Xiao Shaun Wang, Yan Huang, Yongan Zhao, Haixu Tang, XiaoFeng Wang, and Diyue Bu · 2015
Cited alongside, same era.
Deep learning with differential privacy
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang · 2016
Cited alongside, same era.
Edit distance: Sketching, streaming, and document exchange
Djamal Belazzougui and Qin Zhang · 2016
Cited alongside, same era.
Streaming algorithms for computing edit distance without exploiting suffix trees
Diptarka Chakraborty, Elazar Goldenberg, and Michal Kouckỳ · 2016
Cited alongside, same era.
An Improved Sketching Algorithm for Edit Distance
Ce Jin, Jelani Nelson, and Kewen Wu · 2021
Later among the works it cites.
Small-space and streaming pattern matching with k k edits
Tomasz Kociumaka, Ely Porat, and Tatiana Starikovskaya · 2021
Later among the works it cites.
Scalable differential privacy with sparse network finetuning
Zelun Luo, Daniel J Wu, Ehsan Adeli, and Fei-Fei Li · 2021
Later among the works it cites.
Differential privacy for text analytics via natural text sanitization
Xiang Yue, Minxin Du, Tianhao Wang, Yaliang Li, Huan Sun, and Sherman S. M. Chow · 2021
Later among the works it cites.
Levenshtein distance as a measure of accuracy and precision in forensic pcr-mps methods
Brian Young, Tom Faris, and Luigi Armogida · 2021
Later among the works it cites.
Improved Sublinear-Time Edit Distance for Preprocessed Strings
Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos · 2022
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Streaming algorithms for embedding and computing edit distance in the low distance regime
Diptarka Chakraborty, Elazar Goldenberg, and Michal Kouckỳ · 2016
Cited alongside, same era.
Differentially private data releasing for smooth queries
Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang · 2016
Cited alongside, same era.
The bernstein mechanism: function release under differential privacy
Francesco Aldà and Benjamin I.P. Rubinstein · 2017
Cited alongside, same era.
Accurate and nearly optimal sublinear approximations to ulam distance
Timothy Naumovitz, Michael Saks, and C Seshadhri · 2017
Cited alongside, same era.
Dynamic time warping and geometric edit distance: Breaking the quadratic barrier
Omer Gold and Micha Sharir · 2018
Cited alongside, same era.
Syntf: Synthetic and differentially private term frequency vectors for privacy-preserving text mining
Benjamin Weggenmann and Florian Kerschbaum · 2018
Cited alongside, same era.
Differential privacy has disparate impact on model accuracy
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov · 2019
Cited alongside, same era.
Later among the works it cites.
Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer · 2022
Later among the works it cites.
Calibration with privacy in peer review
Wenxin Ding, Gautam Kamath, Weina Wang, and Nihar B. Shah · 2022
Later among the works it cites.
Adversarially robust streaming algorithms via differential privacy
Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer · 2022
Later among the works it cites.
Differentially private multi-party data release for linear regression
Ruihan Wu, Xin Yang, Yuanshun Yao, Jiankai Sun, Tianyi Liu, Kilian Q Weinberger, and Chong Wang · 2022
Later among the works it cites.
Differentially private fine-tuning of language models
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang · 2022
Later among the works it cites.
Differentially private label protection in split learning
Xin Yang, Jiankai Sun, Yuanshun Yao, Junyuan Xie, and Chong Wang · 2022
Later among the works it cites.
Locally consistent decomposition of strings with applications to edit distance sketching
Sudatta Bhattacharya and Michal Kouckỳ · 2023
Later among the works it cites.
Robust algorithms on adaptive inputs from bounded adversaries
Yeshwanth Cherapanamjeri, Sandeep Silwal, David Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou · 2023
Later among the works it cites.
An Algorithmic Bridge Between Hamming and Levenshtein Distances
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha · 2023
Later among the works it cites.
Differentially private attention computation
Yeqi Gao, Zhao Song, and Xin Yang · 2023
Later among the works it cites.
Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability
Zhao Song, Yitan Wang, Zheng Yu, and Lichen Zhang · 2023
Later among the works it cites.
Dpauc: differentially private auc computation in federated learning
Jiankai Sun, Xin Yang, Yuanshun Yao, Junyuan Xie, Di Wu, and Chong Wang · 2023
Later among the works it cites.
Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance
Zhao Song, Xin Yang, Yuanyuan Yang, and Lichen Zhang · 2023
Later among the works it cites.
Fast private kernel density estimation via locality sensitive quantization
Tal Wagner, Yonatan Naamad, and Nina Mishra · 2023
Later among the works it cites.
Efficiently computing similarities to private datasets
Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, and Jakub Tarnawski · 2024
Closest in time.
Almost linear size edit distance sketch
Michal Kouckỳ and Michael E Saks · 2024
Closest in time.
Differentially private kernel density estimation
Erzhi Liu, Jerry Yao-Chieh Hu, Alex Reneau, Zhao Song, and Han Liu · 2024
Closest in time.