Home

Purushottam Kar

  1. Estimating small frequency moments of data stream: a characteristic function approach.

    Mon, 05/10/2010 - 15:01 — SomNambul
    Authors: Purushottam Kar, Sumit Ganguly
    Subjects: Data Structures and Algorithms
    Abstract

    We consider the problem of estimating the first moment of a data stream
    defined as $F_1 = \sum_{i \in \{1,2, ..., n\}} \abs{f_i}$ to within $1\pm
    \epsilon$-relative error with high probability. Several algorithms are
    well-known for this problem including the median estimator over $p$-stable
    sketches by Indyk \cite{indy:focs00}, the geometric means estimator over
    $p$-stable sketches by Li \cite{pinglib:2006} and the \Hss sketch based
    algorithm in \cite{gc:random07}.

  2. On Low Distortion Embeddings of Statistical Distance Measures into Low Dimensional Spaces.

    Fri, 09/18/2009 - 11:36 — SomNambul
    Authors: Arnab Bhattacharya, Purushottam Kar, Manjish Pal
    Subjects: Computational Geometry
    Abstract

    Statistical distance measures have found wide applicability in information
    retrieval tasks that typically involve high dimensional datasets. In order to
    reduce the storage space and ensure efficient performance of queries,
    dimensionality reduction while preserving the inter-point similarity is highly
    desirable. In this paper, we investigate various statistical distance measures
    from the point of view of discovering low distortion embeddings into
    low-dimensional spaces.

Math-arch

Syndicate content