# US 2013/0159328 A1 · Fast Streams and Substreams

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159328 A1
- Document ID: US20130159328A1
- Status: Published application
- Kind: A1
- Application number: 13/328,389
- Filed: 2011-12-16
- Published: 2013-06-20
- Earliest claimed: 2011-12-16
- Assignees: Microsoft Corporation
- Inventors: Christopher C. McConnell
- Web page: https://patentgrep.com/patent/US20130159328A1

## CPC

- G06Q 10/40: Business processes related to social networking or social networking services
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/24552: {Database cache management}
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06Q 30/0201: Market modelling; Market analysis; Collecting market data
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various embodiments provide data structures and algorithms for efficiently computing a time ordered stream that is the combination of a time ordered substream for individual persons of interest. In addition, various embodiments provide an approach for identifying how many changes of interest have happened to a particular stream since it was last viewed.

## Claims

### Claim 1

One or more computer readable storage media embodying computer readable instructions that implement data structures comprising:
persistent data structures and in memory data structures, the data structures being configured to represent streams and sub streams associated with social networking data,
the persistent data structures comprising:
a stream table configured to record history of a plurality of posts and be utilized to initialize one or more in memory data structures;
a following table and cache configured to provide a mapping from a user to people that the user follows; and
a notification position table and cache configured to contain a global position of a last element in a stream returned as a notification for a particular UserID;
the in-memory data structures comprising:
a stream vector that is configured to track stream elements;
a substream start vector configured to be used to look up an index in the stream vector of a newest element in a substream; and
state information associated with stream.

### Claim 2 (depends on 1)

The one or more computer readable storage media of claim 1, wherein the stream table utilizes a schema comprising:
a global position that provides an auto-increment primary key that tracks global order of items that were added to a stream;
a SubStreamID that identifies a sub stream that an item is posted to;
an ItemID that identifies an item being added to a stream; and
metadata associated with individual items.

### Claim 3 (depends on 1)

The one or more computer readable storage media of claim 1, wherein the stream table utilizes a schema comprising:
a global position that provides an auto-increment primary key that tracks global order of items that were added to a stream;
a SubStreamID that identifies a sub stream that an item is posted to;
an ItemID that identifies an item being added to a stream; and
metadata associated with individual items, wherein the metadata comprises a type.

### Claim 4 (depends on 1)

The one or more computer readable storage media of claim 1, wherein the following table utilizes a schema comprising: a UserID that identifies a particular user; and a vector of SubStreamIDs that are being followed.

### Claim 5 (depends on 1)

The one or more computer readable storage media of claim 1, wherein the notification position table and cache utilizes a schema comprising: a UserID associated with a user that is being tracked; and a global position that represents a last element returned as a notification.

### Claim 6 (depends on 1)

The one or more computer readable storage media of claim 1, wherein the stream vector comprises a cache-aligned memory configured as a circular buffer.

### Claim 7 (depends on 1)

The one or more computer readable storage media of claim 1, wherein individual elements in the stream vector have values comprising:
an ItemID that identifies an item in a stream:
a type that identifies a type of an associated ItemID;
a SubStreamID that identifies a sub stream of which a particular element is a part;
a next value that represents an index within the stream vector of the next older element in the substream; and
a previous value that represents an index within the stream vector of the previous newer element in the substream.

### Claim 8 (depends on 1)

The one or more computer readable storage media of claim 1, wherein the state information comprises:
an oldest value that represents an index of an oldest element in the stream vector;
a full value that is configured to represent that a stream vector is full of elements;
a fill value that represents one element before an oldest element that has been inserted into the stream vector during initialization;
a global position value that represents a furthest point in a global sequence of values added; and
a write lock that represents a lock that is used when adding elements to a stream.

### Claim 9

A method comprising:
initializing a plurality of elements in a stream vector associated with social networking data;
reading individual rows in a stream table while a write lock has been acquired; and
responsive to said reading, adding elements to the stream vector, the write lock being configured to allow reading of an associated stream during initialization.

### Claim 10 (depends on 9)

The method of claim 9, wherein the stream vector comprises an in-memory data structure and the stream table is a persistent stream table that maintains a history of a plurality of posts in an associated social network.

### Claim 11 (depends on 9)

The method of claim 9, wherein said reading comprises reading individual rows starting with a most recent row.

### Claim 12 (depends on 9)

The method of claim 9, wherein elements include values comprising:
an ItemID,
a Type,
a SubStreamID,
a SubStreamStart, and
a value associated with no older elements in an associated substream.

### Claim 13 (depends on 9)

The method of claim 9 further comprising inserting a new element into the stream under the influence of a write lock that allows the stream to be read while the new element is inserted.

### Claim 14 (depends on 9)

The method of claim 9 further comprising inserting a new element into the stream under the influence of a write lock that allows the stream to be read while the new element is inserted and, responsive to inserting the new element in the stream, adding the new element to the stream table.

### Claim 15

One or more computer-readable storage media embodying computer readable instructions that implement a method comprising:
iterating over a stream of elements pertaining to a stream of social networking data; and
using a memory barrier during iteration to enable the stream to be read while write operations are taking place.

### Claim 16 (depends on 15)

The one or more computer-readable storage media of claim 15, wherein said using comprises using the memory barrier to ensure that write operations are synchronized across threads.

### Claim 17 (depends on 15)

The one or more computer-readable storage media of claim 15 further comprising returning an element having a desired type.

### Claim 18 (depends on 15)

The one or more computer-readable storage media of claim 15 further comprising using a heap to return elements in order.

### Claim 19 (depends on 15)

The one or more computer-readable storage media of claim 15 further comprising acquiring a write lock, then reading a sub stream associated with the stream, and releasing the write lock.

### Claim 20 (depends on 15)

The one or more computer-readable storage media of claim 15 further comprising generating one or more notifications associated with the stream.
