公开(公告)号：US20120159500A1

公开(公告)日：2012-06-21

申请号：US12971913

申请日：2010-12-17

申请人： Graham Cormode ,  Amit Chakrabarti ,  Ranganath Kondapally ,  Andrew Iain Shaw McGregor

发明人： Graham Cormode ,  Amit Chakrabarti ,  Ranganath Kondapally ,  Andrew Iain Shaw McGregor

IPC分类号： G06F9/46

CPC分类号： G06F11/3688

摘要： A method for validating outsourced processing of a priority queue includes configuring a verifier for independent, single-pass processing of priority queue operations that include insertion operations and extraction operations and priorities associated with each operation. The verifier may be configured to validate N operations using a memory space having a size that is proportional to the square root of N using an algorithm to buffer the operations as a series of R epochs. Extractions associated with each individual epoch may be monitored using arrays Y and Z. Insertions for the epoch k may monitored using arrays X and Z. The processing of the priority queue operations may be verified based on the equality or inequality of the arrays X, Y, and Z. Hashed values for the arrays may be used to test their equality to conserve storage requirements.

摘要翻译： 用于验证优先级队列的外包处理的方法包括配置用于对包括插入操作和提取操作以及与每个操作相关联的优先级的优先级队列操作进行独立，单程处理的验证器。 验证器可以被配置为使用具有与N的平方根成比例的大小的存储器空间来验证N个操作，使用算法将该操作缓冲为一系列R个时期。 可以使用阵列Y和Z来监视与每个单个时期相关联的抽取。可以使用阵列X和Z监视历元k的插入。可以基于阵列X，Y的相等或不等式来验证优先级队列操作的处理 ，并且Z.阵列的哈希值可以用于测试它们的相等性以节省存储要求。

公开(公告)号：US08612649B2

公开(公告)日：2013-12-17

申请号：US12971913

申请日：2010-12-17

申请人： Graham Cormode ,  Amit Chakrabarti ,  Ranganath Kondapally ,  Andrew Iain Shaw McGregor

发明人： Graham Cormode ,  Amit Chakrabarti ,  Ranganath Kondapally ,  Andrew Iain Shaw McGregor

IPC分类号： G06F13/12

CPC分类号： G06F11/3688

摘要： A method for validating outsourced processing of a priority queue includes configuring a verifier for independent, single-pass processing of priority queue operations that include insertion operations and extraction operations and priorities associated with each operation. The verifier may be configured to validate N operations using a memory space having a size that is proportional to the square root of N using an algorithm to buffer the operations as a series of R epochs. Extractions associated with each individual epoch may be monitored using arrays Y and Z. Insertions for the epoch k may monitored using arrays X and Z. The processing of the priority queue operations may be verified based on the equality or inequality of the arrays X, Y, and Z. Hashed values for the arrays may be used to test their equality to conserve storage requirements.

摘要翻译： 用于验证优先级队列的外包处理的方法包括配置用于对包括插入操作和提取操作以及与每个操作相关联的优先级的优先级队列操作进行独立，单程处理的验证器。 验证器可以被配置为使用具有与N的平方根成比例的大小的存储器空间来验证N个操作，使用算法将该操作缓冲为一系列R个时期。 可以使用阵列Y和Z来监视与每个单个时期相关联的抽取。可以使用阵列X和Z监视历元k的插入。可以基于阵列X，Y的相等或不等式来验证优先级队列操作的处理 ，并且Z.阵列的哈希值可以用于测试它们的相等性以节省存储要求。