Return-Path: X-Original-To: apmail-accumulo-user-archive@www.apache.org Delivered-To: apmail-accumulo-user-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id A5D61DCB1 for ; Thu, 18 Oct 2012 14:50:29 +0000 (UTC) Received: (qmail 65259 invoked by uid 500); 18 Oct 2012 14:50:29 -0000 Delivered-To: apmail-accumulo-user-archive@accumulo.apache.org Received: (qmail 65058 invoked by uid 500); 18 Oct 2012 14:50:29 -0000 Mailing-List: contact user-help@accumulo.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: user@accumulo.apache.org Delivered-To: mailing list user@accumulo.apache.org Received: (qmail 65023 invoked by uid 99); 18 Oct 2012 14:50:28 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 18 Oct 2012 14:50:28 +0000 X-ASF-Spam-Status: No, hits=-0.7 required=5.0 tests=RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of jeff.kubina@gmail.com designates 209.85.223.169 as permitted sender) Received: from [209.85.223.169] (HELO mail-ie0-f169.google.com) (209.85.223.169) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 18 Oct 2012 14:50:21 +0000 Received: by mail-ie0-f169.google.com with SMTP id 10so17297959ied.0 for ; Thu, 18 Oct 2012 07:50:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:from:date:message-id:subject:to:content-type; bh=C61LvOxNs4Uz7wlkXpZ/4/QL71xFQkZWBKx0TVpmW/4=; b=oZ2GP4wHYs+C9S6J+OEiMXKi+pZgZxGXE2GiKHCK3CSbPAwZUqn9BT5cmGplKy0JVK /E9s44zLfawWysFZd13V1HWAPO4aVY2aM7wvI3Yzj2KEX00/S1VeTstFWc3GEWW9wGMx +ogKcaf5qUhAVqi/qT4SjRH3R3Djbuct62pZvtZTgA0JpQdv4JBwir8WotSVzTIQLVEt 6wV82SsNn/JbUcKmM0nBwFC2dmewZ71rid9uLixNN0lXnWDpsq3uDrIygMcsl57hcKmm KbfLbwOTZ/WSzK/qEHnTxgx9qrG8Yf2whEx9HP+71jEAgU11r2LTUx65JqAPK500jz+6 GP3g== Received: by 10.50.152.137 with SMTP id uy9mr4988783igb.62.1350571800179; Thu, 18 Oct 2012 07:50:00 -0700 (PDT) MIME-Version: 1.0 Received: by 10.43.95.201 with HTTP; Thu, 18 Oct 2012 07:49:39 -0700 (PDT) From: Jeff Kubina Date: Thu, 18 Oct 2012 10:49:39 -0400 Message-ID: Subject: What is the Communication and Time Complexity for Bulk Inserts? To: user@accumulo.apache.org Content-Type: text/plain; charset=ISO-8859-1 X-Virus-Checked: Checked by ClamAV on apache.org I am deriving the time complexities for an algorithm I implemented in Hadoop using Accumulo and need to know the time complexity of bulk inserting m records evenly distributed across p nodes into an empty table with p tablet servers. Assuming B is the bandwidth of the network, would the communication complexity be O(m/B) and the computation complexity O(m/p * log(m/p))? If the table contained n records would the values be O(m/B) and O(m/p * log(m/p) + n/p)?