At&t Intellectual Property I, L.p.

Microsoft Technology Licensing, LLC

At+t Corp.

Haim Kaplan

Edith Cohen

Nicholas G Duffield

Carsten Lund

Mikkel Thorup

Andrew V Goldberg

Renato F Werneck

Uri Zwick

Nadav Grossaug

Methods and systems for estimate derivation are described. In one embodiment, a query may be received with a predicate for sets over a collection of items. Associated samples associated with the query may be accessed. Items of an associated sample may be accessed from the collection of items. A determination of whether the predicate is an attribute-based selection from a union of at least some sets may be made. Available items of the particular associated sample may be selected from the items. Identified items may be identified among the available items in the associated sample that satisfy the predicate. An adjusted weight may be assigned to an item based on a weight of the item and a distribution of the associated samples. An estimate may be generated based on the adjusted weight of the identified items of the associated samples that satisfy the predicate. Additional methods and systems are disclosed.

Methods and systems to estimate query responses based on data set sketches

A method and apparatus for processing top-k queries are disclosed. For example, the method receives a top-k query with a value for a number of samples and a value of a confidence parameter. The method samples in accordance to the number of samples, and determines a top-k weight of a sample top-k set. The method bounds the top-k weight in an interval having an upper bound and a lower bound such that the top-k weight is in the interval with a probability equal to one minus the value of the confidence parameter, and provides a response to the top-k query in accordance with the upper and lower bounds.

Method and apparatus for processing of top-K queries from samples

A method for producing a summary A of data points in an unaggregated data stream wherein the data points are in the form of weighted keys (a, w) where a is a key and w is a weight, and the summary is a sample of k keys a with adjusted weights w. A first reservoir L includes keys having adjusted weights which are additions of weights of individual data points of included keys and a second reservoir T includes keys having adjusted weights which are each equal to a threshold value &#x3c4; whose value is adjusted based upon tests of new data points arriving in the data stream. The summary combines the keys and adjusted weights of the first reservoir L with the keys and adjusted weights of the second reservoir T to form the sample representing the data stream upon which further analysis may be performed. The method proceeds by first merging new data points in the stream into the reservoir L until the reservoir contains k different keys and thereafter applying a series of tests to new arriving data points to determine what keys and weights are to be added to or removed the reservoirs L and T to provide a summary with a variance that approaches the minimum possible for aggregated data sets. The method is composable, can be applied to high speed data streams such as those found on the Internet, and can be implemented efficiently.

Method for summarizing data in unaggregated data streams

Certain exemplary embodiments can provide a method, which can comprise automatically storing and computing a sketch of a dataset that supports an automatically determined estimator of properties of a dataset. The dataset can be related to any population. For example, the dataset can comprise data flows through a network node (e.g., a router), sales data, and/or marketing data, etc. The estimator can be based upon a sketch of the dataset.

Systems, devices, and/or methods for managing data

Certain exemplary embodiments can provide a method, which can comprise automatically storing a sketch of a dataset that supports automatic determination of an estimator of properties of a dataset. The automatic determination can be based upon computed adjusted weights to the items included in a sketch of the dataset. The adjusted weights can be used to compute estimates on the weight of any subpopulation of the items in the dataset that is specified using a selection predicate. We propose the rank conditioning, the subset conditioning, and/or a Markov-chain based method to compute these adjusted weights. We also provide a method that provides upper and lower confidence bounds on the size of a subpopulation.

Systems, devices, and/or methods for determining dataset estimators

The present invention relates to a method of obtaining a generic sample of an input stream. The method is designated as VAROPT. The method comprises receiving an input stream of items arriving one at a time, and maintaining a sample S of items i. The sample S has a capacity for at most k items i. The sample S is filled with k items i. An nitem i is received. It is determined whether the nitem i should be included in sample S. If the nitem i is included in sample S, then a previously included item i is dropped from sample S. The determination is made based on weights of items without distinguishing between previously included items i and the nitem i. The determination is implemented thereby updating weights of items i in sample S. The method is repeated until no more items are received.

Variance-optimal sampling-based estimation of subset sums

An algorithm referred to as REAL for the point-to-point shortest path problem combines A* search with landmark-based lower bounds and reach-based pruning. A symbiosis of these techniques is described, which gives a range of time and space tradeoffs, including those that improve both of these complexity measures. Locality is improved and exact reach computation is described.

Enhanced reach-based graph processing using shortcuts

The invention relates to streaming algorithms useful for obtaining summaries over unaggregated packet streams and for providing unbiased estimators for characteristics, such as, the amount of traffic that belongs to a specified subpopulation of flows. Packets are sampled from a packet stream and aggregated into flows and counted by implementation of: (a) Adaptive Sampled NetFlow (NF), and adjusted weight (A) of a flow (f) is calculated as follows: A(f)=i(f)/p'; i(f) being the number of packets counted for a flow f, and p&#x2032; being the sampling rate at end of a measurement period; or (b) Adaptive Sample-and-Hold (SH), and adjusted weight (A) of a flow (f) is calculated as follows: A(f)=i(f)+(1&#x2212;p&#x2032;)/p&#x2032;; i(f) being the number of packets counted for a flow f, and p&#x2032; being the sampling rate at end of a measurement period.

Algorithms and estimators for summarization of unaggregated data streams

The invention relates to streaming algorithms useful for obtaining summaries over unaggregated packet streams and for providing unbiased estimators for characteristics, such as, the amount of traffic that belongs to a specified subpopulation of flows. Packets are sampled from a packet stream and aggregated into flows and counted by implementation of Adaptive Sample-and-Hold (SH) or Adaptive NetFlow (NF), adjusting the sampling rate based on a quantity of flows to obtain a sketch having a predetermined size, the sampling rate being adjusted in steps; and transferring the count of aggregated packets from SRAM to DRAM and initializing the count in SRAM following adjustment of the sampling rate.

A method is disclosed for reducing user-perceived latency due to the time required to establish a connection to a server in a network. In accordance with the present invention, an open connection is established to a set of servers, there being some probability the user will contact one of the servers in the near future. This is referred to as preconnecting or prefetching the connection. In the context of a Web client-server network, a list of likely servers can be deduced from links on a current Web page a user is looking at or from a more sophisticated analysis of the user's browsing habits. When the user requests a resource from one of the identified servers, the network connection has already been established, thereby reducing latency and improving service quality, especially for higher bandwidth clients for whom the delay is most noticeable. In contrast to conventional document prefetching, preconnecting does not hog network bandwidth or consume cache space, and hence can be used with much less scrutiny. Moreover, the technique can be implemented in Web browsers without protocol modifications or changes to Web server code.

Growing community of inventors

Hod Hasharon, Israel

Haim Kaplan