公开(公告)号：US20110282865A1

公开(公告)日：2011-11-17

申请号：US12781000

申请日：2010-05-17

申请人： Kunal Talwar ,  Moritz A.W. Hardt

发明人： Kunal Talwar ,  Moritz A.W. Hardt

IPC分类号： G06F17/30

CPC分类号： G06F17/30424

摘要： A system for answering sets of queries on a set of private data while providing differential privacy protection is provided. The set of queries is received and applied to the set of private data to generate a set of results or answers. A geometric representation of the set of queries is generated. Example geometric representations include polytopes. Error values are generated for the set of queries using a K-norm mechanism based on values sampled from the geometric representation. The sampled values are added to the set of results to provide the differential privacy protection. By generating the error values based on the set of queries rather than the set of results or the set of private data, the amount of error added to the generated results to achieve a level of differential privacy protection is reduced.

摘要翻译： 提供一种用于在提供差异隐私保护的情况下应答一组私有数据的查询集的系统。 接收到一组查询并将其应用于私有数据集合以生成一组结果或答案。 生成查询集的几何表示。 示例几何表示包括多面体。 基于从几何表示采样的值，使用K范数机制为查询集生成错误值。 采样值被添加到结果集中，以提供差异隐私保护。 通过基于查询集而不是一组结果或一组私有数据生成错误值，减少了增加到生成结果以达到差异隐私保护水平的错误量。

公开(公告)号：US20100281478A1

公开(公告)日：2010-11-04

申请号：US12433919

申请日：2009-05-01

申请人： Larry Jay Sauls ,  Sanjay Gautam ,  Ehud Wieder ,  Rina Panigrahy ,  Kunal Talwar

发明人： Larry Jay Sauls ,  Sanjay Gautam ,  Ehud Wieder ,  Rina Panigrahy ,  Kunal Talwar

IPC分类号： G06F9/455

CPC分类号： G06F9/5077

摘要： A virtual machine distribution system is described herein that uses a multiphase approach that provides a fast layout of virtual machines on physical computers followed by at least one verification phase that verifies that the layout is correct. During the fast layout phase, the system uses a dimension-aware vector bin-packing algorithm to determine an initial fit of virtual machines to physical hardware based on rescaled resource utilizations calculated against hardware models. During the verification phase, the system uses a virtualization model to check the recommended fit of virtual machine guests to physical hosts created during the fast layout phase to ensure that the distribution will not over-utilize any host given the overhead associated with virtualization. The system modifies the layout to eliminate any identified overutilization. Thus, the virtual machine distribution system provides the advantages of a fast, automated layout planning process with the robustness of slower, exhaustive processes.

摘要翻译： 本文描述了一种虚拟机分配系统，其使用多相方法，其在物理计算机上提供虚拟机的快速布局，之后是验证布局正确的至少一个验证阶段。 在快速布局阶段，系统使用维度感知向量二进制包装算法，根据硬件模型计算的重新定义的资源利用率来确定虚拟机对物理硬件的初始拟合。 在验证阶段，系统使用虚拟化模型来检查虚拟机guest虚拟机对于在快速布局阶段期间创建的物理主机的推荐配置，以确保分配不会过度利用任何与虚拟化相关的开销的主机。 系统修改布局以消除任何确定的过度利用。 因此，虚拟机分配系统提供了快速，自动化的布局规划过程的优点，具有较慢，详尽的过程的鲁棒性。

公开(公告)号：US07788164B2

公开(公告)日：2010-08-31

申请号：US11227454

申请日：2005-09-15

申请人： Kamal Jain ,  Kunal Talwar

发明人： Kamal Jain ,  Kunal Talwar

IPC分类号： G06Q40/00

CPC分类号： G06Q30/02 ,  G06Q30/0251 ,  G06Q30/0273 ,  G06Q30/0275 ,  G06Q30/0277 ,  G06Q30/08 ,  G06Q40/00 ,  G06Q40/04

摘要： To use market clearing methods to determine market equilibrium, a market clearing situation is established by determining a number of items to be sold at the market price and allotting a number of pseudo items assignable to bids below the market price. Once bids are received for the items, using the number of pseudo items and the actual items as the supply side, and the total funds bid as the demand side, a market clearing price is determinable using a market clearing equilibrium model. Funds assigned to pseudo items are returned or not charged. Further, by selling items only to bids exceeding the market clearing price, such as by setting the market price incrementally above the market clearing price, bidders are encouraged to submit bid prices bid reflecting what the items are worth to them instead of attempting to bid strategically to guess or set the market price.

摘要翻译： 为了使用市场清算方法来确定市场均衡，通过确定以市场价格出售的物品数量并分配一些低于市场价格的投标价值的伪品，确定市场清算情况。 一旦收到项目出价，使用伪项目数量和实际项目作为供应方，总资金出价作为需求方，则使用市场清算均衡模型确定市场结算价格。 分配给伪物品的资金将被退回或不收取费用。 此外，如果通过将商品出售超过市场清算价格，例如通过将市场价格逐渐高于市场清算价格，则鼓励投标人提交反映出价格的投标价格，而不是尝试策略性地出价 猜测或设定市场价格。

公开(公告)号：US20060277135A1

公开(公告)日：2006-12-07

申请号：US11145051

申请日：2005-06-03

申请人： Kamal Jain ,  Kunal Talwar

发明人： Kamal Jain ,  Kunal Talwar

IPC分类号： G06Q40/00

CPC分类号： G06Q30/08 ,  G06Q30/02 ,  G06Q30/0275 ,  G06Q40/04

摘要： Auction prices for a quantity of items, the quantity of which is not determined prior to auction, are equilibrated among bidders to reflect supply and demand for the items. For example, in auctioning Internet advertising opportunities, the first available opportunities are auctioned to a high bidder. Later in the course of the auction period, once the high bidder's budget has been exhausted, the price for advertising opportunities is reduced. The difference in price paid by the high bidder and the reduced price for the quantity of advertising opportunities purchased is credited to the high bidder's account. Once the high bidder's account regains a level sufficient to acquire additional advertising opportunities, the high bidder may continue to acquire advertising opportunities. Other bidders similarly are credited the difference between prices previously paid and the current price. An equilibrium price is reached based on the recursive adjustment of prices paid by the bidders.

摘要翻译： 在拍卖前未量化的数量的拍卖价格在投标人之间平衡，以反映物品的供应和需求。 例如，在拍卖互联网广告机会时，第一个可用的机会被拍卖给高出价者。 拍卖期后，一旦投标人的预算用尽，广告机会的价格就会下降。 高投标人支付的价格差异和购买广告机会数量的降低价格记入高出价人的账户。 一旦高投标人的帐户重新获得足够的水平以获得额外的广告机会，高投标人可能会继续获得广告机会。 其他投标人也同样被认为是以前支付的价格与当前价格的差额。 基于投标人支付的价格的递归调整，达到均衡价格。

公开(公告)号：US20110208763A1

公开(公告)日：2011-08-25

申请号：US12712219

申请日：2010-02-25

申请人： Frank D. McSherry ,  Kunal Talwar

发明人： Frank D. McSherry ,  Kunal Talwar

IPC分类号： G06F17/30

CPC分类号： G06F17/30864 ,  G06F21/6245 ,  G06F21/6263

摘要： A query log includes a list of queries and a count for each query representing the number of times that the query was received by a search engine. In order to provide differential privacy protection to the queries, noise is generated and added to each count, and queries that have counts that fall below a threshold are removed from the query log. A distribution associated with a function used to generate the noise is referenced to determine a distribution of a number of times that a hypothetical query having a zero count would have its count exceed the threshold after the addition of noise. Random queries of an amount equal to a sample from the distribution of number of times are added to the query log with a count that is greater than the threshold count.

摘要翻译： 查询日志包括查询列表和每个查询的计数，表示搜索引擎收到查询的次数。 为了向查询提供不同的隐私保护，将生成噪声并将其添加到每个计数中，并且从查询日志中删除具有低于阈值的计数的查询。 参考与用于产生噪声的函数相关联的分布，以确定在添加噪声之后具有零计数的假设查询的计数将超过阈值的次数的分布。 数量等于来自分发次数的样本的随机查询被添加到具有大于阈值计数的计数的查询日志中。

公开(公告)号：US20110067030A1

公开(公告)日：2011-03-17

申请号：US12560452

申请日：2009-09-16

申请人： Michael Isard ,  Vijayan Prabhakaran ,  Jonathan James Currey ,  Ehud Wieder ,  Kunal Talwar

发明人： Michael Isard ,  Vijayan Prabhakaran ,  Jonathan James Currey ,  Ehud Wieder ,  Kunal Talwar

IPC分类号： G06F9/46 ,  G06F15/173

CPC分类号： G06F9/5066 ,  G06F8/433 ,  G06F9/4881

摘要： A job scheduler may schedule concurrent distributed jobs in a computer cluster by assigning tasks from the running jobs to compute nodes while balancing fairness with efficiency. Determining which tasks to assign to the compute nodes may be performed using a network flow graph. The weights on at least some of the edges of the graph encode data locality, and the capacities provide constraints that ensure fairness. A min-cost flow technique may be used to perform an assignment of the tasks represented by the network flow graph. Thus, online task scheduling with locality may be mapped onto a network flow graph, which in turn may be used to determine a scheduling assignment using min-cost flow techniques. The costs may encode data locality, fairness, and starvation-freedom.

摘要翻译： 作业调度器可以通过将运行作业中的任务分配给计算节点，同时平衡公平性和效率，来计划计算机集群中的并发分布式作业。 确定分配给计算节点的任务可以使用网络流程图来执行。 图的至少一些边缘上的权重编码数据位置，并且容量提供确保公平性的约束。 最小成本流技术可用于执行由网络流程图表示的任务的分配。 因此，具有局部性的在线任务调度可以映射到网络流程图上，网络流程图可以用于使用最小成本流技术来确定调度分配。 成本可能会对数据的局部性，公平性和饥饿自由进行编码。

公开(公告)号：US20090132571A1

公开(公告)日：2009-05-21

申请号：US11941081

申请日：2007-11-16

申请人： Mark Steven Manasse ,  Frank D. McSherry ,  Kunal Talwar

发明人： Mark Steven Manasse ,  Frank D. McSherry ,  Kunal Talwar

IPC分类号： G06F17/30

CPC分类号： G06F16/951

摘要： Documents that are near-duplicates may be determined using techniques such as min-hashing. Randomness that is used in these techniques may be based on sequences of bits. The sequences of bits may be generated from a string of bits, with the sequences determined by parsing the string at each occurrence of a particular value, such as the value “1”.

摘要翻译： 几乎重复的文档可以使用诸如分哈希算法的技术来确定。 在这些技术中使用的随机性可以基于比特序列。 可以从一串比特生成比特序列，其中序列通过在每次出现特定值（例如值“1”）时解析字符串来确定。

公开(公告)号：US08332862B2

公开(公告)日：2012-12-11

申请号：US12560452

申请日：2009-09-16

申请人： Michael Isard ,  Vijayan Prabhakaran ,  Jonathan James Currey ,  Ehud Wieder ,  Kunal Talwar

发明人： Michael Isard ,  Vijayan Prabhakaran ,  Jonathan James Currey ,  Ehud Wieder ,  Kunal Talwar

IPC分类号： G06F9/46 ,  G06F15/16 ,  G06F15/173

CPC分类号： G06F9/5066 ,  G06F8/433 ,  G06F9/4881

摘要： A job scheduler may schedule concurrent distributed jobs in a computer cluster by assigning tasks from the running jobs to compute nodes while balancing fairness with efficiency. Determining which tasks to assign to the compute nodes may be performed using a network flow graph. The weights on at least some of the edges of the graph encode data locality, and the capacities provide constraints that ensure fairness. A min-cost flow technique may be used to perform an assignment of the tasks represented by the network flow graph. Thus, online task scheduling with locality may be mapped onto a network flow graph, which in turn may be used to determine a scheduling assignment using min-cost flow techniques. The costs may encode data locality, fairness, and starvation-freedom.

摘要翻译： 作业调度器可以通过将运行作业中的任务分配给计算节点，同时平衡公平性和效率，来计划计算机集群中的并发分布式作业。 确定分配给计算节点的任务可以使用网络流程图来执行。 图的至少一些边缘上的权重编码数据位置，并且容量提供确保公平性的约束。 最小成本流技术可用于执行由网络流程图表示的任务的分配。 因此，具有局部性的在线任务调度可以映射到网络流程图上，网络流程图可以用于使用最小成本流技术来确定调度分配。 成本可能会对数据的局部性，公平性和饥饿自由进行编码。

公开(公告)号：US07958040B2

公开(公告)日：2011-06-07

申请号：US11145051

申请日：2005-06-03

申请人： Kamal Jain ,  Kunal Talwar

发明人： Kamal Jain ,  Kunal Talwar

IPC分类号： G06Q40/00 ,  G06Q30/00

CPC分类号： G06Q30/08 ,  G06Q30/02 ,  G06Q30/0275 ,  G06Q40/04

摘要： Auction prices for a quantity of items, the quantity of which is not determined prior to auction, are equilibrated among bidders to reflect supply and demand for the items. For example, in auctioning Internet advertising opportunities, the first available opportunities are auctioned to a high bidder. Later in the course of the auction period, once the high bidder's budget has been exhausted, the price for advertising opportunities is reduced. The difference in price paid by the high bidder and the reduced price for the quantity of advertising opportunities purchased is credited to the high bidder's account. Once the high bidder's account regains a level sufficient to acquire additional advertising opportunities, the high bidder may continue to acquire advertising opportunities. Other bidders similarly are credited the difference between prices previously paid and the current price. An equilibrium price is reached based on the recursive adjustment of prices paid by the bidders.

摘要翻译： 在拍卖前未量化的数量的拍卖价格在投标人之间平衡，以反映物品的供应和需求。 例如，在拍卖互联网广告机会时，第一个可用的机会被拍卖给高出价者。 拍卖期后，一旦投标人的预算用尽，广告机会的价格就会下降。 高投标人支付的价格差异和购买广告机会数量的降低价格记入高出价人的账户。 一旦高投标人的帐户重新获得足够的水平以获得额外的广告机会，高投标人可能会继续获得广告机会。 其他投标人也同样被认为是以前支付的价格与当前价格的差额。 基于投标人支付的价格的递归调整，达到均衡价格。

公开(公告)号：US20090234734A1

公开(公告)日：2009-09-17

申请号：US12049384

申请日：2008-03-17

申请人： Sreenivas Gollapudi ,  Frank McSherry ,  Rina Panigrahy ,  Kunal Talwar

发明人： Sreenivas Gollapudi ,  Frank McSherry ,  Rina Panigrahy ,  Kunal Talwar

IPC分类号： G06Q30/00 ,  G06F7/06

CPC分类号： G06Q30/08 ,  G06Q30/02 ,  G06Q30/0256

摘要： Advertising slots on a search engine results page may be determined based on keywords and/or results to a user query. Advertisers may use the keywords and/or the results to the query to place their ads into the advertising slots. Rules may be applied to determine how ads are displayed or not displayed. For example, a larger set of keywords may be inferred from the initial set of keywords on which the ad provider placed her bids. This greatly increases the potential reach of an advertiser's ad campaign or a search engine provider's revenue from ad placement.

摘要翻译： 搜索引擎结果页面上的广告位可以基于用户查询的关键字和/或结果来确定。 广告商可以使用查询的关键字和/或结果将广告投放到广告位。 可以应用规则来确定广告的显示方式或不显示。 例如，可以从广告提供商将其出价的关键字的初始集合推断出一组较大的关键字。 这大大增加了广告客户广告系列或搜索引擎提供商的广告展示位置的收入潜力。