Stable distributions, pseudorandom generators, embeddings and data stream computation

Keywords

Pseudorandom generator, Combinatorics, Embedding, Pseudorandom number generator, Bounded function

References

• An Approximate L1-Difference Algorithm for Massive Data StreamsJoan Feigenbaum, Sampath Kannan, Martin J. Strauss — 2002
• Algorithmic applications of low-distortion geometric embeddingsPiotr Indyk — 2001
• Identifying Representative Trends in Massive Time Series Data Sets Using SketchesPiotr Indyk, Nick Koudas, S. Muthukrishnan — 2000
• One-dimensional stable distributionsВ. М. Золотарев — 1986
• Comparing Data Streams Using Hamming Norms (How to Zero In)Graham Cormode, Mayur Datar, Piotr Indyk — 2002
• The fourth moment methodBonnie Berger — 1991
• Software reliability via run-time result-checkingHal Wasserman, Manuel Blum — 1997
• Pseudorandom generators for space-bounded computationsNoam Nisan — 1990
• Min-wise independent permutations (extended abstract)Andrei Broder, Moses Charikar, Alan Frieze — 1998
• Maintaining Stream Statistics over Sliding WindowsMayur Datar, Aristides Gionis, Piotr Indyk — 2002
• Maintaining stream statistics over sliding windows: (extended abstract)Mayur Datar, Aristides Gionis, Piotr Indyk — 2002
• The dimension of almost spherical sections of convex bodiesT. Figiel, Joram Lindenstrauss, Vitali Milman — 1976
• Fast hierarchical clustering and other applications of dynamic closest pairsDavid Eppstein — 1999
• Randomized geometric algorithms and pseudorandom generatorsK. Mulmuley — 1992
• A Method for Simulating Stable Random VariablesJ. Chambers, C. L. Mallows, B. W. Stuck — 1976
• Dimensionality reduction techniques for proximity problemsPiotr Indyk — 2000
• Fast, small-space algorithms for approximate histogram maintenanceAnna C. Gilbert, Sudipto Guha, Piotr Indyk — 2002
• Finding interesting associations without support pruningEdith Cohen, Mayur Datar, Shintaro Fujiwara — 2000
• Dynamic multidimensional histogramsNitin Thaper, Sudipto Guha, Piotr Indyk — 2002
• Random embeddings of Euclidean spaces in sequence spacesGideon Schechtman — 1981

Cited by

• Measuring k-Wise Independence of Streaming DataVladimir Braverman, Rafail Ostrovsky — 2008
• Bounds for Frequency Estimation of Packet StreamsProsenjit Bose, Evangelos Kranakis, Pat Morin — 2003
• Streaming and Sketch Algorithms for Large Data NLPAmit Goyal — 2013
• An incremental data-stream sketch using sparse random projectionsAditya Krishna Menon, Gia Vinh Anh Pham, Sanjay Chawla — 2007
• Hashing-basierte Indizierung: Anwendungsszenarien, Theorie und MethodenBenno Stein, Martin Potthast — 2006
• High Performance Data Mining in Time Series: Techniques and Case StudiesDennis Shasha, Yunyue Zhu — 2004
• A hybrid technique for estimating frequency moments over data streamsŠumit Ganguly — 2004
• Measuring trends and repetitions in data streamsHossein Jowhari — 2012
• Space-Efficient Estimation of Robust Statistics and Distribution TestingSteve Chien, Katrina Ligett, Andrew McGregor — 2010
• A Sketch-based Sampling Algorithm on Sparse DataPing Li, Kenneth Church, Trevor Hastie — 2006
• Sliding Window Computations over Data StreamsBrian Babcock, Mayur Datar, Rajeev Motwani — 2002
• Streaming Algorithms Via ReductionsMichael S. Crouch — 2014
• Managing and Mining Sensor DataCharų C. Aggarwal — 2013
• Explicit Dimension Reduction and Its ApplicationsZohar Karnin, Yuval Rabani, Amir Shpilka — 2011
• Computing Diameter in the Streaming and Sliding-Window ModelsJoan Feigenbaum, Sampath Kannan, Jian Zhang — 2002
• Dimension reduction techniques for ℓp, 1 ≤ p < ∞, with applicationsYair Bartal, Lee-Ad Gottlieb — 2014
• A PCA-based Data Stream Reduction Scheme for Sensor NetworksAlexander Fedoseev, Younghwan Choi, Eenjun Hwang — 2009
• Taylor Polynomial Estimator for Estimating Frequency MomentsŠumit Ganguly — 2015
• SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny IndexYifang Sun, Wei Wang, Jianbin Qin — 2014
• Sign Stable Random Projections for Large-Scale LearningPing Li — 2015

Related papers

• Pseudorandom NumbersJeffrey C. Lagarias — 1993
• Pseudorandom Generators from Polarizing Random WalksEshan Chattopadhyay, Pooya Hatami, Kaave Hosseini — 2018
• A Pseudorandom Generator from any One-way FunctionJohan Håstad, Russell Impagliazzo, Leonid A. Levin — 1999
• A Single Pseudorandom FunctionBabak Sadeghiym, Josef Pieprzyk — 1993
• A construction of the simplest super pseudorandom permutation generatorEon-Kyung Lee, Kyeong Ja Kim, U Jin Choi — 1995