At&t Intellectual Property I, L.p.

Other

Columbia University

Howard Karloff

Lukasz Golab

Divesh Srivastava

Philip Korn

Rittwik Jana

Nemmara K Shankaranarayanan

Jia Wang

Vaneet Aggarwal

Vinay Anant Vaishampayan

David Lee Applegate

Mohammad Taghi Hajiaghayi

Mohammad Hossein Bateni

Robert Margolies

Ashwin Sridharan

David Johnson

Gil Zussman

Bei Yu

Gruia Calinescu

Katrina Ligett

Barna Saha

Avishek Saha

A method, computer-readable storage device, and apparatus for allocating a plurality of timeslots of each channel of a plurality of channels in a wireless network are disclosed. For example, the method determines a location and a velocity for each user endpoint device of a plurality of user endpoint devices, estimates a future data rate for each user endpoint device at the location, estimates future timeslot allocations of each channel of the plurality of channels in the wireless network in accordance with the future data rate that is predicted for each user endpoint device, and allocates each timeslot of the plurality of timeslots of each channel of the plurality of channels in the wireless network to a user endpoint device of the plurality of user endpoint devices in accordance with the future timeslot allocations that are estimated for each channel.

Method, computer-readable storage device, and apparatus for allocating timeslots on channels in a wireless network

Given a set of data for which a conservation law is an appropriate characterization, 'hold' and/or 'fail' tableaux are provided for the underlying conservation law, thereby providing a conservation dependency whereby portions of the data for which the law approximately holds or fails can be discovered and summarized in a semantically meaningful way.

Conservation dependencies

Data tables in data warehouses are updated to minimize staleness and stretch of the data tables. New data is received from external sources and, in response, update requests are generated. Accumulated update requests may be batched. Data tables may be weighted to affect the order in which update requests are serviced.

Minimizing staleness in real-time data warehouses

The specification describes data processes for analyzing large data steams for target anomalies. 'Sequential dependencies' (SDs) are chosen for ordered data and present a framework for discovering which subsets of the data obey a given sequential dependency. Given an interval G, an SD on attributes X and Y, written as X&#x2192;G Y, denotes that the distance between the Y-values of any two consecutive records, when sorted on X, are within G. SDs may be extended to Conditional Sequential Dependencies (CSDs), consisting of an underlying SD plus a representation of the subsets of the data that satisfy the SD. The conditional approximate sequential dependencies may be expressed as pattern tableaux, i.e., compact representations of the subsets of the data that satisfy the underlying dependency.

Processing data using sequential dependencies

Techniques are disclosed for generating conditional functional dependency (CFD) pattern tableaux having the desirable properties of support, confidence and parsimony. These techniques include both a greedy algorithm for generating a tableau and, for large data sets, an 'on-demand' algorithm that outperforms the basic greedy algorithm in running time by an order of magnitude. In addition, a range tableau, as a generalization of a pattern tableau, can achieve even more parsimony.

Generating conditional functional dependencies

A geometric model is considered for the problem of minimizing access control lists (ACLs) in network routers. A colored rectilinear pattern is created within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. The method operates on rectangular rule lists (RRLs) and access control lists (ACLs) in which all rectangles are strips that extend either the full length or the full height of the canvas. A polynomial-time algorithm optimally constructs such patterns when, as in the ACL application, the only colors are black and white (permit or deny). That algorithm is complemented by a significantly faster approximation algorithm that is guaranteed to be no worse than 3/2 optimal.

Compressing rectilinear pictures and minimizing access control lists

Given a set of network nodes B that are sought to be monitored, and a set of potential monitoring nodes, a subset M of the monitoring nodes is chosen that insures monitoring each node b in B with a pair of nodes mand msuch that no node except b is on both any shortest path from b to mand on any shortest path from b to m. Some of the nodes in M are chosen in a first step by identifying a subset of B having nodes b that are 't-good' nodes, choosing a subset of potential monitoring nodes as First Partner nodes, and choosing a corresponding subset of potential monitoring nodes as Second Partner nodes. Others are chosen in a second step that handles nodes b that are not 't-good,' using a greedy algorithm.

Method for selecting nodes in a network

Growing community of inventors

New York, NY, United States of America

Howard Karloff